// LeetCode 主站 Problem Nr. 148: 排序链表

/*
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
	输入：head = [4,2,1,3]
	输出：[1,2,3,4]

示例 2：
	输入：head = [-1,5,3,4,0]
	输出：[-1,0,3,4,5]

示例 3：
	输入：head = []
	输出：[]

提示：
    链表中节点的数目在范围 [0, 5 * 104] 内
    -105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"

	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func sortList(head *ListNode) *ListNode {
	return method1(head)
}

// 时间复杂度：平方级；空间复杂度：线性级
func method1(head *ListNode) *ListNode {
	length := 0
	sentinel := head
	for sentinel != nil {
		length++
		sentinel = sentinel.Next
	}

	values := make([]*ListNode, length)
	index := 0
	sentinel = head
	for sentinel != nil {
		values[index] = sentinel
		index++
		sentinel = sentinel.Next
	}

	// 冒泡排序
	for i := 0; i < length; i++ {
		for j := i+1; j < length; j++ {
			if values[i].Val > values[j].Val {
				values[i], values[j] = values[j], values[i]
			}
		} 
	}

	sentinel = &ListNode{
		Val: -1,
		Next: nil,
	}

	pointer := sentinel
	for _, v := range values {
		pointer.Next = v
		v.Next = nil
		pointer = pointer.Next
	}

	return sentinel.Next
}

func main() {
	head := ds.BuildSinglyLinkedList([]int{4,2,1,3})
	fmt.Println(head.ToList())
	head = sortList(head)
	fmt.Println(head.ToList())
}
